﻿
using System;
using System.Collections.Generic;
using System.IO;

namespace Maze
{
    
    public class Maze
    {
        
        bool[,] maze; 
        int xSize;
        int ySize;
        Point start;
        Point end;
        
        static void Main(string[] args)
        {
            Maze maze = new Maze();
            maze.Run(args[0]);
            //Console.WriteLine("Press any key to continue.");
            //Console.Read();
        }
        
        void Run(string filePath)
        {
            LoadFromFile(filePath);
            List<List<Point>> solutions = Solve();
            if (solutions.Count == 0)
            {
                Console.WriteLine("No solution");
            }
            else 
            {
                List<Point> best = BestPath(solutions);
                Print(best);
            }
        }
        
        void LoadFromFile(string filePath)
        {
            StreamReader stream = new StreamReader(filePath);
            string line = stream.ReadLine();
            string[] words = line.Split(' ');
            xSize = int.Parse(words[0]);
            ySize = int.Parse(words[1]);
            line = stream.ReadLine();
            start = new Point(line);
            line = stream.ReadLine();
            end = new Point(line);
            maze = new bool[xSize, ySize];
            for (int y = 0; y < ySize; y++)
            {
                line = stream.ReadLine();
                words = line.Split(' ');
                for (int x = 0; x < xSize; x++)
                {
                    int val = int.Parse(words[x]);
                    maze[x, y] = 1==val ? true: false;
                }
            }
            stream.Close();
        }
        
        
        List<List<Point>> Solve()
        {
            List<Point> path = new List<Point>(new List<Point>{start});
            List<List<Point>> unresolvedPaths = new List<List<Point>>();
            unresolvedPaths.Add(path);
            List<List<Point>> resolvedPaths = new List<List<Point>>();
            while (unresolvedPaths.Count > 0)
            {
                List<Point> unresolvedPath = unresolvedPaths[unresolvedPaths.Count-1];
                List<List<Point>> candidatePaths = CandidatePaths(unresolvedPath);
                foreach (List<Point> candidatePath in candidatePaths)
                {
                    if (end.Equals(candidatePath[candidatePath.Count-1]))
                    {
                        resolvedPaths.Add(candidatePath);
                    }
                    else 
                    {
                        unresolvedPaths.Add(candidatePath);
                    }
                }
                // fix me: use SortedSet for better perf
                // need to make class List<Point> implement IComparable
                // to achieve this.
                unresolvedPaths.Remove(unresolvedPath);
            }
            return resolvedPaths;
        }
        
        void Print(List<Point> path)
        {
            // fix me: use char instead of string
            string[,] output = new string[xSize, ySize];
            for (int y = 0; y < ySize; y++)
            {
                for (int x = 0; x < xSize; x++)
                {
                    output[x,y] = maze[x, y] ? "#": " ";
                }
            }
            foreach (Point point in path)
            {
                output[point.X,point.Y] = "X";
            }
            output[start.X, start.Y] = "S";
            output[end.X, end.Y] = "E";
            for (int y = 0; y < ySize; y++)
            {
                for (int x = 0; x < xSize; x++)
                {
                    Console.Write(output[x, y]);
                }
                Console.WriteLine();
            }
        }
               
        List<List<Point>> CandidatePaths(List<Point> path)
        {
            List<List<Point>> candidatePaths = new List<List<Point>>();
            List<Point> candidatePoints = CandidatePoints(path);
            foreach (Point candidatePoint in candidatePoints)
            {
                List<Point> candidatePath = new List<Point>(path);
                candidatePath.Add(candidatePoint);
                candidatePaths.Add(candidatePath);
            }
            return candidatePaths;
        }
        
        List<Point> BestPath(List<List<Point>> paths)
        {
            int min = -1;
            int minIndex = -1;
            for (int i = 0; i < paths.Count; i++)
            {
                List<Point> path = paths[i];
                if (0 == i ||path.Count < min)
                {
                    min = path.Count;
                    minIndex = i;
                }
            }
            return paths[minIndex];
        }
        
        List<Point> CandidatePoints(List<Point> path)
        {
            List<Point> validCandidates = new List<Point>();
            List<Point> candidates = new List<Point>();
            Point last = path[path.Count-1];
            candidates.Add(new Point(last.X  , last.Y+1));
            candidates.Add(new Point(last.X  , last.Y-1));
            candidates.Add(new Point(last.X+1, last.Y  ));
            candidates.Add(new Point(last.X-1, last.Y  ));
            foreach(Point candidate in candidates)
            {
                if (CandidateValid(path, candidate))
                {
                    validCandidates.Add(candidate);
                }                
            }
            return validCandidates;
        }
        
        bool CandidateValid(List<Point> path, Point candidate)
        {
            if (ValidPoint(candidate))
            {
                foreach (Point breadcrumb in path)
                {
                    if(breadcrumb.Equals(candidate))
                    {
                        // retraced steps
                        return false;
                    }
                }
                return true;
            }
            else 
            {
                // wall or out of bounds
                return false;
            }
        }
                    
        bool ValidPoint(Point point)
        {
            if (point.X < 0 || point.X >= xSize || point.Y < 0 || point.Y >= ySize)
            {
                return false;
            }
            else 
            {
                return !maze[point.X, point.Y];
            }
        }
        
        public struct Point:IComparable<Point>
        {
            public int X;
            public int Y;
            
            public Point (int x, int y)
            {
                X = x;
                Y = y;
            }
            
            public Point(string line)
            {
                string[] words = line.Split(' ');
                X = int.Parse(words[0]);
                Y = int.Parse(words[1]);
            }
            
            public override bool Equals(Object obj)
            {
                Point other = (Point)obj;
                return other.X == X && other.Y == Y;
            }
                
            public override int GetHashCode() 
            {
                return X ^ Y;
            }
            
            public int CompareTo(Point other)
            {
                int compare = X.CompareTo(other.X);
                if (0 == compare)
                {
                    compare = Y.CompareTo(other.Y);
                }
                return compare;
            }
        }
    }
}